package org.everyday;

import com.common.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @version v1.0.0
 * 创建时间：2022/8/5 09:22
 */
public class L623 {
    public TreeNode addOneRow(TreeNode root, int val, int depth) {
        if (depth==1){
            TreeNode left = root;
            TreeNode newRoot = new TreeNode(val);
            newRoot.left = left;
            return newRoot;
        }
        Deque<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int level = 1;
        while (!queue.isEmpty()){
            if (level == depth-1) break;
            Deque<TreeNode> temp = new LinkedList<>();
            while (!queue.isEmpty()){
                TreeNode pop = queue.pop();
                if (pop.left!=null) temp.add(pop.left);
                if (pop.right!=null) temp.add(pop.right);
            }
            queue = temp;
            level++;
        }

        // 保存获取下一层的节点
        Deque<TreeNode> nextLevel = new LinkedList<>();
        Deque<TreeNode> preLevel = new LinkedList<>(queue);
        while (!queue.isEmpty()){
            TreeNode pop = queue.pop();
            nextLevel.add(pop.left);
            nextLevel.add(pop.right);
        }
        queue.clear();
        Deque<TreeNode> finalQueue = queue;
        preLevel.forEach(node ->{
            node.left = new TreeNode(val);
            node.right = new TreeNode(val);
            finalQueue.add(node.left);
            finalQueue.add(node.right);
        });
        // 给新增的行 添加节点
        final int[] i = {0};
        finalQueue.forEach(treeNode -> {
            if (i[0] %2==0){
                treeNode.left = nextLevel.pop();
            }else{
                treeNode.right = nextLevel.pop();
            }
            i[0]++;
        });
        return root;
    }

    public static void main(String[] args) {
        TreeNode root = TreeNode.buildTree(new Integer[]{4,2,null,3,1});
        new L623().addOneRow(root,1,3);
        System.out.println(root);
    }
}
